package J5924;

import java.util.Arrays;

/**
 * 网格中机器人回家的最小代价
 *
 * @author 23737
 * @time 2021.11.28
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().minCost(new int[]{1, 0}, new int[]{2, 3}, new int[]{5, 4, 3}, new int[]{8, 2, 6, 7}));
        System.out.println(new Solution().minCost(new int[]{0, 0}, new int[]{0, 0}, new int[]{5}, new int[]{26}));
        System.out.println(new Solution().minCost(new int[]{0, 0}, new int[]{1, 2}, new int[]{10, 2, 5}, new int[]{10, 6, 1}));
    }
}

/**
 * dp写不出来
 */
class Solution {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        //说明已经在家了
        if (Arrays.equals(startPos, homePos)) {
            return 0;
        }

        //define
        int[][] dp = new int[homePos[0] + 1][homePos[1] + 1];

        //init
        for (int i = startPos[0]; i < homePos[0]; i++) {
            dp[i][0] = rowCosts[i + 1];
        }
        for (int j = startPos[1]; j < homePos[1]; j++) {
            dp[0][j] = colCosts[j + 1];
        }

        //dp
        for (int i = startPos[0] + 1; i < homePos[0]; i++) {
            for (int j = startPos[1] + 1; j <= homePos[1]; j++) {
                if (i == startPos[0] && j == startPos[1] + 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
//                System.out.println("dp[i][j]  --> "+dp[i][j]);
            }
        }
        int result = dp[homePos[0] - 1][homePos[1] - 1];
        return result;
    }
}

class Solution2 {
    public int minCost(int[] startPos, int[] homePos, int[] rowCosts, int[] colCosts) {
        // 计算机器人到家的纵向和横向距离
        int disX = startPos[0] - homePos[0];    // 纵向距离
        int disY = startPos[1] - homePos[1];    // 横向距离

        int ans = 0;

        // 计算纵向距离的代价
        if (disX < 0) {
            for (int i = startPos[0] + 1; i <= homePos[0]; i++) {
                ans += rowCosts[i];
            }
        } else {
            for (int i = startPos[0] - 1; i >= homePos[0]; i--) {
                ans += rowCosts[i];
            }
        }

        // 计算横向距离的代价
        if (disY < 0) {
            for (int j = startPos[1] + 1; j <= homePos[1]; j++) {
                ans += colCosts[j];
            }
        } else {
            for (int j = startPos[1] - 1; j >= homePos[1]; j--) {
                ans += colCosts[j];
            }
        }
        return ans;
    }
}


